package cn.bellychang.leetcode.question033;

/**
 * @author ChangLiang
 * @date 2021/3/15
 */
public class Solution3 {

    public int search(int[] nums, int target) {

        int begin = 0;
        int end = nums.length - 1;

        while (begin <= end) {

            int mid = ((end - begin) >> 1) + begin;

            // 说明右侧是有序的
            if (nums[mid] < nums[end]) {

                if(nums[mid] > target){
                    end = mid - 1;
                } else if (nums[end] < target) {
                    end = mid - 1;
                } else {
                    if (nums[mid] == target) {
                        return mid;
                    } else if (nums[mid] > target) {
                        end = mid - 1;
                    } else {
                        begin = mid + 1;
                    }
                }
            }else{
                if (nums[begin] > target) {
                    begin = mid + 1;
                } else if (nums[mid] < target) {
                    begin = mid + 1;
                } else {
                    if (nums[mid] == target) {
                        return mid;
                    } else if (nums[mid] > target) {
                        end = mid - 1;
                    } else {
                        begin = mid + 1;
                    }
                }
            }
        }

        return -1;
    }
}
